// Copyright (C) 2024 Kumo inc.
// Author: Jeff.li lijippy@163.com
// All rights reserved.
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published
// by the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.
//
// This closed addressing hash-map puts first linked node in bucket array
// directly to save an extra memory indirection. As a result, this map yields
// close performance to raw array on nearly all operations, probably being the
// fastest hashmap for small-sized key/value ever.
//
// Performance comparisons between several maps:
// [ value = 8 bytes ]
// Sequentially inserting 100 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/20/300/290/2010/210/230
// Sequentially erasing 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/20/1700/150/160/170/250
// Sequentially inserting 1000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 16/15/360/342/206/195/219
// Sequentially erasing 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 15/18/178/159/149/159/149
// Sequentially inserting 10000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 15/15/415/410/200/192/235
// Sequentially erasing 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 14/17/201/181/151/181/154
// [ value = 32 bytes ]
// Sequentially inserting 100 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/10/280/280/250/200/230
// Sequentially erasing 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/10/2070/150/160/160/160
// Sequentially inserting 1000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 17/17/330/329/207/185/212
// Sequentially erasing 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/17/172/163/146/157/148
// Sequentially inserting 10000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 17/17/405/406/197/185/215
// Sequentially erasing 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/16/206/188/158/168/159
// [ value = 128 bytes ]
// Sequentially inserting 100 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/30/290/290/420/220/250
// Sequentially erasing 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/10/180/150/160/160/160
// Sequentially inserting 1000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 22/25/352/349/213/193/222
// Sequentially erasing 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/17/170/165/160/171/157
// Sequentially inserting 10000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 21/24/416/422/210/206/242
// Sequentially erasing 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 16/16/213/190/163/171/159
// [ value = 8 bytes ]
// Randomly inserting 100 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/20/290/260/250/220/220
// Randomly erasing 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/20/240/220/170/170/180
// Randomly inserting 1000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 16/15/315/309/206/191/215
// Randomly erasing 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 15/17/258/240/155/193/156
// Randomly inserting 10000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 15/16/378/363/208/191/210
// Randomly erasing 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 14/16/311/290/162/187/169
// [ value = 32 bytes ]
// Randomly inserting 100 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/20/280/270/240/230/220
// Randomly erasing 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 10/20/250/220/170/180/160
// Randomly inserting 1000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 18/18/310/304/209/192/209
// Randomly erasing 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/16/255/247/155/175/152
// Randomly inserting 10000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 17/17/381/367/209/197/214
// Randomly erasing 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 15/17/310/296/163/188/168
// [ value = 128 bytes ]
// Randomly inserting 100 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 30/40/300/290/280/230/230
// Randomly erasing 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/20/230/220/160/180/170
// Randomly inserting 1000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 29/33/327/329/219/197/220
// Randomly erasing 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 14/16/257/247/159/182/156
// Randomly inserting 10000 into FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 35/39/398/400/220/213/246
// Randomly erasing 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 35/36/330/319/221/224/200
// [ value = 8 bytes ]
// Seeking 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 10/20/140/130/60/70/50
// Seeking 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/13/172/161/77/54/46
// Seeking 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/16/216/211/73/56/51
// [ value = 32 bytes ]
// Seeking 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 10/20/130/130/70/60/50
// Seeking 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/13/174/163/73/54/49
// Seeking 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/13/218/217/75/58/52
// [ value = 128 bytes ]
// Seeking 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/10/140/130/80/50/60
// Seeking 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/13/173/171/73/55/49
// Seeking 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 26/22/238/252/107/89/91
// [ value = 8 bytes ]
// Seeking 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/10/140/130/70/50/60
// Seeking 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/14/180/160/68/57/47
// Seeking 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/13/221/210/72/57/51
// [ value = 32 bytes ]
// Seeking 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 20/10/140/130/70/60/50
// Seeking 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/13/167/160/69/53/50
// Seeking 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 15/14/224/219/75/59/52
// [ value = 128 bytes ]
// Seeking 100 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 10/10/140/130/80/50/60
// Seeking 1000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 13/13/170/167/70/54/52
// Seeking 10000 from FlatMap/MultiFlatMap/std::map/turbo::PooledMap/std::unordered_map/std::unordered_multimap/turbo::hash_map takes 26/22/238/240/85/70/67
#pragma once

#include <stdint.h>
#include <functional>
#include <iostream>                               // std::ostream
#include <type_traits>                            // std::aligned_storage
#include <turbo/meta/type_traits.h>
#include <turbo/log/logging.h>
#include <turbo/memory/single_threaded_pool.h>            // SingleThreadedPool
#include <turbo/container/hash_tables.h>          // hash<>
#include <turbo/container/internal/bit_array.h>                       // bit_array_*
#include <turbo/memory/scope_guard.h>

namespace turbo {

    template<typename _Map, typename _Element>
    class FlatMapIterator;

    template<typename _Map, typename _Element>
    class SparseFlatMapIterator;

    template<typename K, typename T>
    class FlatMapElement;

    struct FlatMapVoid {
    }; // Replace void which is not constructible.
    template<typename K>
    struct DefaultHasher;
    template<typename K>
    struct DefaultEqualTo;

    struct BucketInfo {
        size_t longest_length;
        double average_length;
    };

    // NOTE: Objects stored in FlatMap MUST be copyable.
    template<typename _K, typename _T,
            // Compute hash code from key.
            // Use murmurhash3 to make better distributions.
            typename _Hash = DefaultHasher<_K>,
            // Test equivalence between stored-key and passed-key.
            // stored-key is always on LHS, passed-key is always on RHS.
            typename _Equal = DefaultEqualTo<_K>,
            bool _Sparse = false,
            typename _Alloc = PtAllocator,
            // If `_Multi' is true, allow containing multiple copies of each key value.
            bool _Multi = false>
    class FlatMap {
    public:
        typedef _K key_type;
        typedef _T mapped_type;
        typedef _Alloc allocator_type;
        typedef FlatMapElement<_K, _T> Element;
        typedef typename Element::value_type value_type;
        typedef typename std::conditional<
                _Sparse, SparseFlatMapIterator<FlatMap, value_type>,
                FlatMapIterator<FlatMap, value_type> >::type iterator;
        typedef typename std::conditional<
                _Sparse, SparseFlatMapIterator<FlatMap, const value_type>,
                FlatMapIterator<FlatMap, const value_type> >::type const_iterator;
        typedef _Hash hasher;
        typedef _Equal key_equal;
        struct PositionHint {
            size_t nbucket;
            size_t offset;
            bool at_entry;
            key_type key;
        };

        explicit FlatMap(const hasher &hashfn = hasher(),
                         const key_equal &eql = key_equal(),
                         const allocator_type &alloc = allocator_type());

        ~FlatMap();

        FlatMap(const FlatMap &rhs);

        FlatMap &operator=(const FlatMap &rhs);

        void swap(FlatMap &rhs);

        // Must be called to initialize this map, otherwise insert/operator[]
        // crashes, and seek/erase fails.
        // `nbucket' is the initial number of buckets. `load_factor' is the
        // maximum value of size()*100/nbucket, if the value is reached, nbucket
        // will be doubled and all items stored will be rehashed which is costly.
        // Choosing proper values for these 2 parameters reduces costs.
        int init(size_t nbucket, u_int load_factor = 80);

        // Insert a pair of |key| and |value|. If size()*100/bucket_count() is
        // more than load_factor(), a resize() will be done.
        // Returns address of the inserted value, nullptr on error.
        mapped_type *insert(const key_type &key, const mapped_type &value);

        // Insert a pair of {key, value}. If size()*100/bucket_count() is
        // more than load_factor(), a resize() will be done.
        // Returns address of the inserted value, nullptr on error.
        mapped_type *insert(const std::pair<key_type, mapped_type> &kv);

        // For `_Multi=false'. (Default)
        // Remove |key| and all associated value
        // Returns: 1 on erased, 0 otherwise.
        template<typename K2, bool Multi = _Multi>
        typename std::enable_if<!Multi, size_t>::type
        erase(const K2 &key, mapped_type *old_value = nullptr);

        // For `_Multi=true'.
        // Returns: num of value on erased, 0 otherwise.
        template<typename K2, bool Multi = _Multi>
        typename std::enable_if<Multi, size_t>::type
        erase(const K2 &key, std::vector<mapped_type> *old_values = nullptr);

        // Remove all items. Allocated spaces are NOT returned by system.
        void clear();

        // Remove all items and return all allocated spaces to system.
        void clear_and_reset_pool();

        // Search for the value associated with |key|.
        // If `_Multi=false', Search for any of multiple values associated with |key|.
        // Returns: address of the value.
        template<typename K2>
        mapped_type *seek(const K2 &key) const;

        template<typename K2>
        std::vector<mapped_type *> seek_all(const K2 &key) const;

        // For `_Multi=false'. (Default)
        // Get the value associated with |key|. If |key| does not exist,
        // insert with a default-constructed value. If size()*100/bucket_count()
        // is more than load_factor, a resize will be done.
        // Returns reference of the value
        template<bool Multi = _Multi>
        typename std::enable_if<!Multi, mapped_type &>::type operator[](const key_type &key);

        // Resize this map. This is optional because resizing will be triggered by
        // insert() or operator[] if there're too many items.
        // Returns successful or not.
        bool resize(size_t nbucket);

        // Iterators
        iterator begin();

        iterator end();

        const_iterator begin() const;

        const_iterator end() const;

        // Iterate FlatMap inconsistently in more-than-one passes. This is used
        // in multi-threaded environment to divide the critical sections of
        // iterating big maps into smaller ones. "inconsistently" means that:
        //  * elements added during iteration may be missed.
        //  * some elements may be iterated more than once.
        //  * iteration is restarted at beginning when the map is resized.
        // Example: (copying all keys in multi-threaded environment)
        //   LOCK;
        //   size_t n = 0;
        //   for (Map::const_iterator it = map.begin(); it != map.end(); ++it) {
        //     if (++n >= 256/*max iterated one pass*/) {
        //       Map::PositionHint hint;
        //       map.save_iterator(it, &hint);
        //       n = 0;
        //       UNLOCK;
        //       LOCK;
        //       it = map.restore_iterator(hint);
        //       if (it == map.begin()) { // resized
        //         keys->clear();
        //       }
        //       if (it == map.end()) {
        //         break;
        //       }
        //     }
        //     keys->push_back(it->first);
        //   }
        //   UNLOCK;
        void save_iterator(const const_iterator &, PositionHint *) const;

        const_iterator restore_iterator(const PositionHint &) const;

        // True if init() was successfully called.
        bool initialized() const { return _buckets != nullptr; }

        bool empty() const { return _size == 0; }

        size_t size() const { return _size; }

        size_t bucket_count() const { return _nbucket; }

        u_int load_factor() const { return _load_factor; }

        // Returns #nodes of longest bucket in this map. This scans all buckets.
        BucketInfo bucket_info() const;

        struct Bucket {
            explicit Bucket(const _K &k) : next(nullptr) { new(&element_spaces) Element(k); }

            Bucket(const Bucket &other) : next(nullptr) { new(&element_spaces) Element(other.element()); }

            bool is_valid() const { return next != (const Bucket *) -1UL; }

            void set_invalid() { next = (Bucket *) -1UL; }

            // NOTE: Only be called when is_valid() is true.
            Element &element() {
                void *spaces = &element_spaces; // Suppress strict-aliasing
                return *reinterpret_cast<Element *>(spaces);
            }

            const Element &element() const {
                const void *spaces = &element_spaces;
                return *reinterpret_cast<const Element *>(spaces);
            }

            Bucket *next;
            typename std::aligned_storage<sizeof(Element), alignof(Element)>::type
                    element_spaces;
        };

        allocator_type &get_allocator() { return _pool.get_allocator(); }

    private:
        template<typename _Map, typename _Element> friend
        class FlatMapIterator;

        template<typename _Map, typename _Element> friend
        class SparseFlatMapIterator;

        struct NewBucketsInfo {
            NewBucketsInfo()
                    : buckets(nullptr), thumbnail(nullptr), nbucket(0) {}

            NewBucketsInfo(Bucket *b, uint64_t *t, size_t n)
                    : buckets(b), thumbnail(t), nbucket(n) {}

            Bucket *buckets;
            uint64_t *thumbnail;
            size_t nbucket;
        };

        NewBucketsInfo new_buckets_and_thumbnail(size_t size, size_t new_nbucket);

        // For `_Multi=true'.
        // Insert a new default-constructed associated with |key| always.
        // If size()*100/bucket_count() is more than load_factor,
        // a resize will be done.
        // Returns reference of the value
        template<bool Multi = _Multi>
        typename std::enable_if<Multi, mapped_type &>::type operator[](const key_type &key);

        // True if buckets need to be resized before holding `size' elements.
        bool is_too_crowded(size_t size) const {
            return is_too_crowded(size, _nbucket, _load_factor);
        }

        static bool is_too_crowded(size_t size, size_t nbucket, u_int load_factor) {
            return size * 100 >= nbucket * load_factor;
        }

        static void init_buckets_and_thumbnail(
                Bucket *buckets, uint64_t *thumbnail, size_t nbucket) {
            for (size_t i = 0; i < nbucket; ++i) {
                buckets[i].set_invalid();
            }
            buckets[nbucket].next = nullptr;
            if (_Sparse) {
                bit_array_clear(thumbnail, nbucket);
            }
        }

        size_t _size;
        size_t _nbucket;
        Bucket *_buckets;
        uint64_t *_thumbnail;
        u_int _load_factor;
        hasher _hashfn;
        key_equal _eql;
        SingleThreadedPool<sizeof(Bucket), 1024, 16, allocator_type> _pool;
    };

    template<typename _K, typename _T,
            typename _Hash = DefaultHasher<_K>,
            typename _Equal = DefaultEqualTo<_K>,
            bool _Sparse = false,
            typename _Alloc = PtAllocator>
    using MultiFlatMap = FlatMap<_K, _T, _Hash, _Equal, _Sparse, _Alloc, true>;

    template<typename _K,
            typename _Hash = DefaultHasher<_K>,
            typename _Equal = DefaultEqualTo<_K>,
            bool _Sparse = false,
            typename _Alloc = PtAllocator>
    class FlatSet {
    public:
        typedef FlatMap<_K, FlatMapVoid, _Hash, _Equal, _Sparse, _Alloc> Map;
        typedef typename Map::key_type key_type;
        typedef typename Map::value_type value_type;
        typedef typename Map::Bucket Bucket;
        typedef typename Map::iterator iterator;
        typedef typename Map::const_iterator const_iterator;
        typedef typename Map::hasher hasher;
        typedef typename Map::key_equal key_equal;
        typedef typename Map::allocator_type allocator_type;

        explicit FlatSet(const hasher &hashfn = hasher(),
                         const key_equal &eql = key_equal(),
                         const allocator_type &alloc = allocator_type())
                : _map(hashfn, eql, alloc) {}

        void swap(FlatSet &rhs) { _map.swap(rhs._map); }

        int init(size_t nbucket, u_int load_factor = 80) { return _map.init(nbucket, load_factor); }

        const void *insert(const key_type &key) { return _map.insert(key, FlatMapVoid()); }

        template<typename K2>
        size_t erase(const K2 &key) { return _map.erase(key, nullptr); }

        void clear() { return _map.clear(); }

        void clear_and_reset_pool() { return _map.clear_and_reset_pool(); }

        template<typename K2>
        const void *seek(const K2 &key) const { return _map.seek(key); }

        bool resize(size_t nbucket) { return _map.resize(nbucket); }

        iterator begin() { return _map.begin(); }

        iterator end() { return _map.end(); }

        const_iterator begin() const { return _map.begin(); }

        const_iterator end() const { return _map.end(); }

        bool initialized() const { return _map.initialized(); }

        bool empty() const { return _map.empty(); }

        size_t size() const { return _map.size(); }

        size_t bucket_count() const { return _map.bucket_count(); }

        u_int load_factor() const { return _map.load_factor(); }

        BucketInfo bucket_info() const { return _map.bucket_info(); }

    private:
        Map _map;
    };

    template<typename _K, typename _T,
            typename _Hash = DefaultHasher<_K>,
            typename _Equal = DefaultEqualTo<_K> >
    class SparseFlatMap : public FlatMap<_K, _T, _Hash, _Equal, true> {
    };

    template<typename _K,
            typename _Hash = DefaultHasher<_K>,
            typename _Equal = DefaultEqualTo<_K> >
    class SparseFlatSet : public FlatSet<_K, _Hash, _Equal, true> {
    };

// Implement FlatMapElement
    template<typename K, typename T>
    class FlatMapElement {
    public:
        typedef std::pair<const K, T> value_type;

        // NOTE: Have to initialize _value in this way which is treated by GCC
        // specially that _value is zeroized(POD) or constructed(non-POD). Other
        // methods do not work. For example, if we put _value into the std::pair
        // and do initialization by calling _pair(k, T()), _value will be copy
        // constructed from the defaultly constructed instance(not zeroized for
        // POD) which is wrong generally.
        explicit FlatMapElement(const K &k) : _key(k), _value(T()) {}

        //                                             ^^^^^^^^^^^
        const K &first_ref() const { return _key; }

        T &second_ref() { return _value; }

        T &&second_movable_ref() { return std::move(_value); }

        value_type &value_ref() { return *reinterpret_cast<value_type *>(this); }

        inline static const K &first_ref_from_value(const value_type &v) { return v.first; }

        inline static const T &second_ref_from_value(const value_type &v) { return v.second; }

        inline static T &&second_movable_ref_from_value(value_type &v) { return std::move(v.second); }

    private:
        const K _key;
        T _value;
    };

    template<typename K>
    class FlatMapElement<K, FlatMapVoid> {
    public:
        typedef const K value_type;

        explicit FlatMapElement(const K &k) : _key(k) {}

        const K &first_ref() const { return _key; }

        FlatMapVoid &second_ref() { return second_ref_from_value(_key); }

        FlatMapVoid &second_movable_ref() { return second_ref(); }

        value_type &value_ref() { return _key; }

        inline static const K &first_ref_from_value(value_type &v) { return v; }

        inline static FlatMapVoid &second_ref_from_value(value_type &) {
            static FlatMapVoid dummy;
            return dummy;
        }

        inline static const FlatMapVoid &second_movable_ref_from_value(value_type &v) {
            return second_ref_from_value(v);
        }

    private:
        K _key;
    };

// Implement DefaultHasher and DefaultEqualTo
    template<typename K>
    struct DefaultHasher : public TURBO_HASH_NAMESPACE::hash<K> {
    };

    template<>
    struct DefaultHasher<std::string> {
        std::size_t operator()(const std::string_view &s) const {
            std::size_t result = 0;
            for (std::string_view::const_iterator
                         i = s.begin(); i != s.end(); ++i) {
                result = result * 101 + *i;
            }
            return result;
        }

        std::size_t operator()(const char *s) const {
            std::size_t result = 0;
            for (; *s; ++s) {
                result = result * 101 + *s;
            }
            return result;
        }

        std::size_t operator()(const std::string &s) const {
            std::size_t result = 0;
            for (std::string::const_iterator i = s.begin(); i != s.end(); ++i) {
                result = result * 101 + *i;
            }
            return result;
        }
    };

    template<typename K>
    struct DefaultEqualTo : public std::equal_to<K> {
    };

    template<>
    struct DefaultEqualTo<std::string> {
        bool operator()(const std::string &s1, const std::string &s2) const { return s1 == s2; }

        bool operator()(const std::string &s1, const std::string_view &s2) const { return s1 == s2; }

        bool operator()(const std::string &s1, const char *s2) const { return s1 == s2; }
    };

}  // namespace turbo

#include <turbo/container/flat_map_inl.h>

